package com.liuqing.www.寻路算法;

import java.util.ArrayList;
import java.util.List;

/**
 * http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html
 * http://www.policyalmanac.org/games/aStarTutorial.htm
 * A*算法确实是最高效、最流行的寻路算法,是搜索算法最深层的延伸.A*算法是由4个要素组成:A*=估价函数+并查集+堆+广搜.想要写A*算法,我们必须门心自问对这4个方面的基本功打的怎么样?因此，A*算法不是所有开发者都能享受的,这种高深的算法必须有强大的算法功底和长年累月的实战积累才能实现.另外,A*也不是最适合的算法.是的，我前面确实说过A*是最高效、最流行的算法,但是指的是它在不同运用领域所表现出来的更强的通用性,指的是基于数据统计它的性能期望最高.
 * 那么A*是否适合移植到android平台呢?我们需要来分析它的特点与专长.A*算法的精髓是以空间换时间,它的运用前提是:解空间充分大,运算时间有限,而存储空间(一般是内存)相对充足.当我们将它移植到手机平台,手机极其珍贵稀缺的内存资源,使A*失去了用武之地;其二,手机游戏的寻路空间相对较小,解空间相对狭隘,因此,搜索算法的瓶颈不再是冗余的搜索消耗,而估价函数的开销以及较长实现代码将成为新的瓶颈.因此，A*算法并不是android手机游戏的唯一选择,针对不同的搜索需要，我们应该定制不同的搜索算法.
 * 
 * 对于涉及算法不是太深的开发者,其实不必追求华丽的A*,写一个普通的宽搜或者广搜就OK,毕竟手机游戏的解空间与PC游戏差了不止一个数量集.大家唯一要做的,只是做好减枝和优化就行了.开发寻路算法的大门永远都向我们敞开着,只要我们选准了突破方向.
 * 对于算法牛人来说,我们需要分类探讨.对于解空间较小，及时性较高的游戏，采用A*是最恰当的选择.如果解空间较大,内存空间紧缺,那么采用跌代加深搜索更好.如果是持续寻路(比如NPC每走一步,都要寻找一次最优路径),那么遗传算法是再适合不过的选择
 * 
 * @author 韩世超
 * 
 */
public class A_shap {
	/*开启列表就像一张购物清单。
	你的路径可能会通过它包含的方格，也可能不会。
	基本上，这是一个待检查方格的列表。
	F = G + H 
	x,y,0:0和1标示是否删除掉
	x,y,1：G = 从起点 A 移动到指定方格的移动代价，沿着到达该方格而生成的路径。 
	x,y,2：H = 从指定的方格移动到终点 B 的估算成本。这个通常被称为试探法，
	x,y,3：F = G + H 
	x,y,4：父节点
	*/
	private static int[][] trueloop;
	private static int[][][] openlist;
	private static int openlistlength;
	/*关闭的列表*/
	static int index=0;
	static boolean  falg;
	private static boolean closeList[][];
	private static int closeListlength;
	private static int[][] a = {// 1可以，0不可以
	{ 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1 }, 
	{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
	{ 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
	{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1 },
	{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
	{ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 }, };
	static int bbx=1,bby=1,eex=1,eey=9;
	public static void main(String[] args) {
		lookUpWayPoint(bbx,bby,eex,eey);
		for(int i=0;i<trueloop.length;i++){
			for(int j=0;j<trueloop[i].length;j++){
				System.out.print(trueloop[i][j]+" ");
			}
			System.out.println();
		}
	}
	public static void lookUpWayPoint(int bx,int by,int ex,int ey){
		if((a.length<bx+1)||(a[0].length<by+1)){
			System.out.println("地图表为空或者起始位置不存在");
		}
		if((a.length<ex+1)||(a[0].length<ex+1)){
			System.out.println("地图表为空或者结束位置不存在");
		}
		if(a[bx][by]==0||a[ex][ey]==0){
			System.out.println("起始位置或者结束未知为无法到达的位置");
		}
		openlist=new int[a.length][a[0].length][5];
		trueloop=new int[a.length][a[0].length];
		closeList = new boolean[a.length][a[0].length];
		int x=bx-ex;
		int y=by-ey;
		if(x<y){
			falg=false;
		}
		for(int i=0;i<a.length;i++){
			for(int j=0;j<a[i].length;j++){
				trueloop[i][j]=a[i][j];
				openlist[i][j][0]=0;//0为不开启
				openlist[i][j][1]=Math.abs(bx-i)+Math.abs(by-j);//从开始点到本地的
				if(falg)
				openlist[i][j][2]=Math.abs(ex-i);//从结束点到本地的
				else
					openlist[i][j][2]=Math.abs(ey-j);//从结束点到本地的
			}
		}
		addOpenlist(bx,by);
		toLookUpWay(bx,by,ex,ey);
		
	}
	static void toLookUpWay(int bx,int by,int ex,int ey){
		if(bx==ex&&by==ey){
			System.out.println("寻路结束......");
			finishLookWay(bx,by,bbx,bby);
			return ;
		}
		index++;
//		if(index==30){
//			return;
//		}
		openNode(bx,by);
		int minf=20000;
		for(int i = 0; i < a.length; i++){
			for(int j = 0; j < a[i].length; j++){
				if(openlist[i][j][0] == 1){
					if(minf>=openlist[i][j][3]){
						minf = openlist[i][j][3];
						bx = i;by = j;
					}
				}
			}
		}
	toLookUpWay(bx,by,ex,ey);
	}
	public static void finishLookWay(int fx,int fy,int bx,int by){
		trueloop[fx][fy]=2;
		if(fx==bx&&fy==by){
			System.out.println("找到点");
			return;
		}
//		System.out.println(fx+","+fy);
		int father=openlist[fx][fy][4];//取得父节点
		if(father==0){
			System.out.println("错误.....");
			return;
		}
		switch(father){
			case 1://在父亲上面
				fy=fy+1;
				break;
			case 2://在原点上面
				fy=fy-1;
				break;
			case 3://在原点上面
				fx=fx+1;
				break;
			case 4://在原点上面
				fx=fx-1;
				break;
		}
		finishLookWay(fx,fy,bx,by);
	}
	/**
	 * openlist设为0
	 * openlistlength--
	 * closeList true
	 * closeListlength++
	 */
	static void openNode(int x,int y){
		openlist[x][y][0]=0;
		openlistlength--;
		closeList[x][y]=true;
		closeListlength++;
		if(checkCanOpen(x+1,y)){//右
			addOpenlist(x+1,y);
			setFather(x+1,y,4);
			setFGH(x+1,y);
		}
		if(checkCanOpen(x-1,y)){//左
			addOpenlist(x-1,y);
			setFather(x-1,y,3);
			setFGH(x-1,y);
		}
		if(checkCanOpen(x,y+1)){//下
			addOpenlist(x,y+1);
			setFather(x,y+1,2);
			setFGH(x,y+1);
		}
		if(checkCanOpen(x,y-1)){//上
			addOpenlist(x,y-1);
			setFather(x,y-1,1);
			setFGH(x,y-1);
		}
		System.out.println();
	}
	static void setFGH(int x,int y ){
		
		switch(openlist[x][y][4])
		{
			default:
				break;
			case 1://在原点上面
				openlist[x][y][1]=openlist[x][y+1][1]+1;
				openlist[x][y][3]=openlist[x][y][1]+openlist[x][y][2];
				break;
			case 2://在原点下面
				openlist[x][y][1]=openlist[x][y-1][1]+1;
				openlist[x][y][3]=openlist[x][y][1]+openlist[x][y][2];
				break;
			case 3://在原点左面
				openlist[x][y][1]=openlist[x+1][y][1]+1;
				openlist[x][y][3]=openlist[x][y][1]+openlist[x][y][2];
				break;
			case 4://在原点右面
				openlist[x][y][1]=openlist[x-1][y][1]+1;
				openlist[x][y][3]=openlist[x][y][1]+openlist[x][y][2];
				break;
		}
			System.out.print(x+","+y+":"+openlist[x][y][1]+"  ");	
	}
	/**
	 * 0本身 1上，2下，3左，4右
	 */
	static void setFather(int x,int y,int num){
		openlist[x][y][4]=num;
	}
	/**
	 * oplist中，设值为1，长度++
	 */
	static void addOpenlist(int x,int y){
		openlist[x][y][0]=1;
		openlistlength++;
	}
	/**
	 * 判断是否可以打开
	 */
	static boolean checkCanOpen(int x,int y){
		if(x<0||y<0||(x>(a.length-1))||(y>(a[x].length-1))){
			return false;
		}
		
		if(openlist[x][y][0]==1){//已经打开过
			return false;
		}
		if(a[x][y]==0){//为不可通过路径
			return false;
		}
		if(closeList[x][y]==true){//在关闭列表中
			return false;
		}
		return true;
	}
}